package lc.二叉树;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @author: qian
 * @createDate: 2021/10/17
 */
public class Math230_二叉搜索树中第K小的元素 {
    int i = 0;
    int res = 0;
    // 剪枝
    public int kthSmallest(TreeNode root, int k) {
        bfs(root,k);
        return res;
    }

    private void bfs(TreeNode root,int k) {

        if (root == null) {
            return;
        }
        bfs(root.left, k);
        i++;
        if (i == k) {
            res = root.val;
        }
        bfs(root.right, k);


    }

    // 全部遍历
    public int kthSmallest1(TreeNode root, int k) {

        List<Integer> list = new ArrayList<>();
        bfs(list,root);
        return list.get(k - 1);
    }

    private void bfs(List<Integer> list, TreeNode root) {

        if (root == null) {
            return;
        }
        bfs(list,root.left);
        list.add(root.val);
        bfs(list,root.right);
    }
}
